package exercises.leetcode;

import exercises.newcoder.util.ListNode;

import java.util.LinkedList;
import java.util.concurrent.Executors;

/**
 * <a href="https://leetcode-cn.com/problems/add-two-numbers-ii/">
 * 445. 两数相加 II</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 * <p>
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 * <p>
 *  
 * <p>
 * 示例1：
 * <p>
 * <img src="https://pic.leetcode-cn.com/1626420025-fZfzMX-image.png">
 * <p>
 * 输入：l1 = [7,2,4,3], l2 = [5,6,4]
 * 输出：[7,8,0,7]
 * <p>
 * 示例2：
 * <p>
 * 输入：l1 = [2,4,3], l2 = [5,6,4]
 * 输出：[8,0,7]
 * <p>
 * 示例3：
 * <p>
 * 输入：l1 = [0], l2 = [0]
 * 输出：[0]
 *  
 * <p>
 * 提示：
 * <ul>
 * <li>链表的长度范围为 [1, 100]</li>
 * <li>0 <= node.val <= 9</li>
 * <li>输入数据保证链表代表的数字无前导 0</li>
 * </ul>
 * 进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。
 *
 * @author or2
 * @date 2021年10月05日 时间: 20:22
 */
public class No445 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        var stackFor1 = new LinkedList<Integer>();
        var stackFor2 = new LinkedList<Integer>();

        for (; l1 != null; l1 = l1.next)
            stackFor1.push(l1.val);
        for (; l2 != null; l2 = l2.next)
            stackFor2.push(l2.val);

        l1 = null; l2 = null; Executors.newSingleThreadExecutor().submit(System::gc);

        ListNode resHead = new ListNode(0);
        int carry = 0;
        while (!stackFor1.isEmpty() && !stackFor2.isEmpty()) {
            int sum = stackFor1.pop() + stackFor2.pop();
            if (carry == 1) {
                sum++;
                carry = 0;
            }
            if (sum > 9) {
                carry = 1;
                sum -= 10;
            }

            resHead.next = new ListNode(sum, resHead.next);
        }

        while (!stackFor1.isEmpty())
            resHead.next = new ListNode(stackFor1.pop(), resHead.next);
        while (!stackFor2.isEmpty())
            resHead.next = new ListNode(stackFor2.pop(), resHead.next);

        return resHead.next;
    }
}
